class Solution
{
public:
    double maxAverageRatio(vector<vector<int>> &classes, int extraStudents)
    {
        auto compare = [](auto &class1, auto &class2)
        {
            return (class1[1] + 1) * class1[1] * (class2[1] - class2[0]) >
                   (class2[1] + 1) * class2[1] * (class1[1] - class1[0]);
        };
        priority_queue<array<long long, 2>, vector<array<long long, 2>>, decltype(compare)> q(compare);
        for (auto &c : classes)
        {
            q.push({c[0], c[1]});
        }

        for (int i = 0; i < extraStudents; ++i)
        {
            auto [pass, total] = q.top();
            q.pop();
            q.push({pass + 1, total + 1});
        }

        double totalRatio = 0.0;
        while (!q.empty())
        {
            auto c = q.top();
            q.pop();
            totalRatio += 1.0 * c[0] / c[1];
        }
        return totalRatio / classes.size();
    }

    // 这题卡vector时间，会超时
    double maxAverageRatio(vector<vector<int>> &classes, int extraStudents)
    {
        auto compare = [](auto &class1, auto &class2)
        {
            return (class1[1] + 1) * class1[1] * (class2[1] - class2[0]) >
                   (class2[1] + 1) * class2[1] * (class1[1] - class1[0]);
        };
        priority_queue<vector<long long>, vector<vector<long long>>, decltype(compare)> q(compare);
        for (auto &c : classes)
        {
            q.push({c[0], c[1]});
        }

        for (int i = 0; i < extraStudents; ++i)
        {
            auto maxIncRatioClass = q.top();
            q.pop();
            q.push({maxIncRatioClass[0] + 1, maxIncRatioClass[1] + 1});
        }

        double totalRatio = 0.0;
        while (!q.empty())
        {
            auto c = q.top();
            q.pop();
            totalRatio += 1.0 * c[0] / c[1];
        }
        return totalRatio / classes.size();
    }
};